package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	var list []*TreeNode // the path to p
	// find p
	n := root
	for n != nil {
		list = append(list, n)
		if n == p {
			break
		} else if p.Val < n.Val {
			n = n.Left
		} else {
			n = n.Right
		}
	}
	for i := len(list) - 1; i >= 0; i-- {
		n = list[i]
		result := n
		for n != nil {
			if n == q {
				return result
			}
			if q.Val < n.Val {
				n = n.Left
			} else {
				n = n.Right
			}
		}
	}
	return nil
}

func main() {
	n0 := &TreeNode{Val: 6}
	n1 := &TreeNode{Val: 2}
	n2 := &TreeNode{Val: 8}
	n3 := &TreeNode{Val: 0}
	n4 := &TreeNode{Val: 4}
	n0.Left = n1
	n0.Right = n2
	n1.Left = n3
	n1.Right = n4
	result := lowestCommonAncestor(n0, n1, n4)
	println(result.Val)
}
